home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / KPlib 1.3.5 / KPSet.h < prev    next >
Text File  |  1995-12-17  |  14KB  |  555 lines
  1. // A module of KPlib v1.3.5.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_SET_DEFINED
  6. #define KP_SET_DEFINED
  7.  
  8. #include <stdlib.h>
  9. #include "KPbasic.h"
  10. #include "KPList.h"
  11.  
  12. // Assumes Element has a default constructor, operator=(), operator==(),
  13. // and operator<().  Note that operator<() must place a total ordering on
  14. // the set of Elements.
  15.  
  16. // All union, intersection and difference operations are of order O(n).
  17.  
  18. template <class Element>
  19. class KPSet {
  20.     public:
  21.         KPSet();
  22.         KPSet(const KPSet<Element> &set);
  23.         KPSet(const KPList<Element> &list);
  24.         KPSet(const Element &element);
  25.         ~KPSet();
  26.         operator KPList<Element>() const;
  27.  
  28.         // Union
  29.         KPSet<Element> operator+(const KPSet<Element> &set) const;
  30.         KPSet<Element> operator+(const Element &element) const;
  31.         KPSet<Element> &operator+=(const KPSet<Element> &set);
  32.         KPSet<Element> &operator+=(const Element &element);
  33.         KPSet<Element> &add(const KPSet<Element> &set);
  34.         KPSet<Element> &add(const Element &element);
  35.  
  36.         // Intersection
  37.         KPSet<Element> operator*(const KPSet<Element> &set) const;
  38.         KPSet<Element> operator*(const Element &element) const;
  39.         KPSet<Element> &operator*=(const KPSet<Element> &set);
  40.         KPSet<Element> &operator*=(const Element &element);
  41.  
  42.         // Difference
  43.         KPSet<Element> operator-(const KPSet<Element> &set) const;
  44.         KPSet<Element> operator-(const Element &element) const;
  45.         KPSet<Element> &operator-=(const KPSet<Element> &set);
  46.         KPSet<Element> &operator-=(const Element &element);
  47.  
  48.         // Miscellaneous
  49.         bool operator==(const KPSet<Element> &set) const;
  50.         bool operator!=(const KPSet<Element> &set) const;
  51.         bool operator<(const KPSet<Element> &set) const; // NOT subset function
  52.         KPSet<Element> &operator=(const KPSet<Element> &set);
  53.         KPSet<Element> &operator=(const Element &element);
  54.         KPSet<Element> &operator=(const KPList<Element> &list);
  55.         const KPList<Element> &list() const;
  56.         int size() const;
  57.         bool is_empty() const;
  58.         bool contains(const KPSet<Element> &set) const;
  59.         bool contains(const Element &element) const;
  60.         KPSet<Element> all_such_that(bool (*f)(const Element &)) const;
  61.         Element retrieve();  // Returns and removes an element.
  62.         KPSet<Element> &clear();
  63.     protected:
  64.         KPSortableList<Element> my_list;
  65. };
  66.  
  67. /****************************************************************************/
  68.  
  69. template <class Element>
  70. inline
  71. KPSet<Element>::KPSet(): my_list()
  72. { /* do nothing */ }
  73.  
  74. /****************************************************************************/
  75.  
  76. template <class Element>
  77. inline
  78. KPSet<Element>::KPSet(const KPSet<Element> &set): my_list(set.my_list)
  79. { /* do nothing */ }
  80.  
  81. /****************************************************************************/
  82.  
  83. template <class Element>
  84. inline
  85. KPSet<Element>::KPSet(const KPList<Element> &list)
  86. {
  87.     *this = list;
  88. }
  89.  
  90. /****************************************************************************/
  91.  
  92. template <class Element>
  93. inline
  94. KPSet<Element>::KPSet(const Element &element): my_list(element)
  95. { /* do nothing */ }
  96.  
  97. /****************************************************************************/
  98.  
  99. template <class Element>
  100. inline
  101. KPSet<Element>::~KPSet()
  102. {
  103.     my_list.clear();
  104. }
  105.  
  106. /****************************************************************************/
  107.  
  108. template <class Element>
  109. inline
  110. KPSet<Element>::operator KPList<Element>() const
  111. {
  112.     return my_list;
  113. }
  114.  
  115. /****************************************************************************/
  116.  
  117. template <class Element>
  118. inline KPSet<Element>
  119. KPSet<Element>::operator+(const KPSet<Element> &set) const
  120. {
  121.     KPSet<Element> new_set(*this);
  122.     new_set += set;
  123.     return new_set;
  124. }
  125.  
  126. /****************************************************************************/
  127.  
  128. template <class Element>
  129. inline KPSet<Element>
  130. KPSet<Element>::operator+(const Element &element) const
  131. {
  132.     KPSet<Element> new_set(*this);
  133.     new_set += element;
  134.     return new_set;
  135. }
  136.  
  137. /****************************************************************************/
  138.  
  139. template <class Element>
  140. KPSet<Element> &
  141. KPSet<Element>::operator+=(const KPSet<Element> &set)
  142. {
  143.     if (this == &set)
  144.         return *this;
  145.  
  146.     KPIterator<Element> a(my_list);
  147.     KPReadOnlyIterator<Element> b(set.my_list);
  148.  
  149.     while (b.ptr()) {
  150.         while (a.ptr() && *a < *b)
  151.             a++;
  152.         if (!a.ptr()) {
  153.             for (; b.ptr(); b++)
  154.                 my_list.add_to_tail(*b);
  155.         }
  156.         else {
  157.             if (*a == *b)
  158.                 a++;
  159.             else
  160.                 a.insert_before_current(*b);
  161.             b++;
  162.         }
  163.     }
  164.  
  165.     return *this;
  166. }
  167.  
  168. /****************************************************************************/
  169.  
  170. template <class Element>
  171. KPSet<Element> &
  172. KPSet<Element>::operator+=(const Element &element)
  173. {
  174.     KPIterator<Element> iter(my_list);
  175.  
  176.     // Start looking from the end of the list, in case the elements are
  177.     // being added in alphabetical order.
  178.  
  179.     iter.end();
  180.     while (iter.ptr() && element < *iter)
  181.         --iter;
  182.     if (!iter.ptr())
  183.         my_list.add_to_head(element);
  184.     else if (!(*iter == element))
  185.         iter.insert_after_current(element);
  186.  
  187.     return *this;
  188. }
  189.  
  190. /****************************************************************************/
  191.  
  192. template <class Element>
  193. inline KPSet<Element> &
  194. KPSet<Element>::add(const KPSet<Element> &set)
  195. {
  196.     return *this += set;
  197. }
  198.  
  199. /****************************************************************************/
  200.  
  201. template <class Element>
  202. inline KPSet<Element> &
  203. KPSet<Element>::add(const Element &element)
  204. {
  205.     return *this += element;
  206. }
  207.  
  208. /****************************************************************************/
  209.  
  210. template <class Element>
  211. inline KPSet<Element>
  212. KPSet<Element>::operator*(const KPSet<Element> &set) const
  213. {
  214.     if (this == &set)
  215.         return *this;
  216.  
  217.     KPSet<Element> new_set;
  218.     KPReadOnlyIterator<Element> a(my_list), b(set.my_list);
  219.  
  220.     while (b.ptr()) {
  221.         while (a.ptr() && *a < *b)
  222.             a++;
  223.         if (!a.ptr()) {
  224.             b.end();
  225.             b++;
  226.         }
  227.         else {
  228.             if (*a == *b) {
  229.                 new_set.my_list.add_to_tail(*a);
  230.                 a++;
  231.             }
  232.             b++;
  233.         }
  234.     }
  235.     return new_set;
  236. }
  237.  
  238. /****************************************************************************/
  239.  
  240. template <class Element>
  241. inline KPSet<Element>
  242. KPSet<Element>::operator*(const Element &element) const
  243. {
  244.     KPSet<Element> new_set;
  245.     if (contains(element))
  246.         new_set.my_list = element;
  247.     return new_set;
  248. }
  249.  
  250. /****************************************************************************/
  251.  
  252. template <class Element>
  253. KPSet<Element> &
  254. KPSet<Element>::operator*=(const KPSet<Element> &set)
  255. {
  256.     if (this == &set)
  257.         return *this;
  258.  
  259.     KPIterator<Element> a(my_list);
  260.     KPReadOnlyIterator<Element> b(set.my_list);
  261.  
  262.     while (b.ptr()) {
  263.         while (a.ptr() && *a < *b)
  264.             a++;
  265.         if (!a.ptr()) {
  266.             b.end();
  267.             b++;
  268.         }
  269.         else {
  270.             if (!(*a == *b)) {
  271.                 a.remove_current();
  272.                 a++;
  273.             }
  274.             b++;
  275.         }
  276.     }
  277.     return *this;
  278. }
  279.  
  280. /****************************************************************************/
  281.  
  282. template <class Element>
  283. inline KPSet<Element> &
  284. KPSet<Element>::operator*=(const Element &element)
  285. {
  286.     if (contains(element))
  287.         my_list = element;
  288.     else
  289.         my_list.clear();
  290.  
  291.     return *this;
  292. }
  293.  
  294. /****************************************************************************/
  295.  
  296. template <class Element>
  297. KPSet<Element>
  298. KPSet<Element>::operator-(const KPSet<Element> &set) const
  299. {
  300.     KPSet<Element> new_set;
  301.  
  302.     if (this == &set)
  303.         return new_set;
  304.  
  305.     KPReadOnlyIterator<Element> a(my_list), b(set.my_list);
  306.  
  307.     while (a.ptr()) {
  308.         while (b.ptr() && *b < *a)
  309.             b++;
  310.         if (!b.ptr())
  311.             while (a.ptr()) {
  312.                 new_set.my_list.add_to_tail(*a);
  313.                 a++;
  314.             }
  315.         else {
  316.             if (!(*a == *b))
  317.                 new_set.my_list.add_to_tail(*a);
  318.             else
  319.                 b++;
  320.             a++;
  321.         }
  322.     }
  323.     return new_set;
  324. }
  325.  
  326. /****************************************************************************/
  327.  
  328. template <class Element>
  329. inline KPSet<Element>
  330. KPSet<Element>::operator-(const Element &element) const
  331. {
  332.     KPSet<Element> new_set(*this);
  333.     new_set -= element;
  334.     return new_set;
  335. }
  336.  
  337. /****************************************************************************/
  338.  
  339. template <class Element>
  340. KPSet<Element> &
  341. KPSet<Element>::operator-=(const KPSet<Element> &set)
  342. {
  343.     if (this == &set) {
  344.         my_list.clear();
  345.         return *this;
  346.     }
  347.  
  348.     KPIterator<Element> a(my_list);
  349.     KPReadOnlyIterator<Element> b(set.my_list);
  350.  
  351.     while (b.ptr()) {
  352.         while (a.ptr() && *a < *b)
  353.             a++;
  354.         if (!a.ptr()) {
  355.             b.end();
  356.             b++;
  357.         }
  358.         else {
  359.             if (*a == *b) {
  360.                 a.remove_current();
  361.                 a++;
  362.             }
  363.             b++;
  364.         }
  365.     }
  366.     return *this;
  367. }
  368.  
  369. /****************************************************************************/
  370.  
  371. template <class Element>
  372. KPSet<Element> &
  373. KPSet<Element>::operator-=(const Element &element)
  374. {
  375.     KPIterator<Element> iter(my_list);
  376.  
  377.     while (iter.ptr() && *iter < element)
  378.         iter++;
  379.     if (iter.ptr() && *iter == element)
  380.         iter.remove_current();
  381.  
  382.     return *this;
  383. }
  384.  
  385. /****************************************************************************/
  386.  
  387. template <class Element>
  388. inline bool
  389. KPSet<Element>::operator==(const KPSet<Element> &set) const
  390. {
  391.     return my_list == set.my_list;
  392. }
  393.  
  394. /****************************************************************************/
  395.  
  396. template <class Element>
  397. inline bool
  398. KPSet<Element>::operator!=(const KPSet<Element> &set) const
  399. {
  400.     return my_list != set.my_list;
  401. }
  402.  
  403. /****************************************************************************/
  404.  
  405. template <class Element>
  406. inline bool
  407. KPSet<Element>::operator<(const KPSet<Element> &set) const
  408. {
  409.     return my_list < set.my_list;
  410. }
  411.  
  412. /****************************************************************************/
  413.  
  414. template <class Element>
  415. inline KPSet<Element> &
  416. KPSet<Element>::operator=(const KPSet<Element> &set)
  417. {
  418.     my_list = set.my_list;
  419.     return *this;
  420. }
  421.  
  422. /****************************************************************************/
  423.  
  424. template <class Element>
  425. inline KPSet<Element> &
  426. KPSet<Element>::operator=(const Element &element)
  427. {
  428.     my_list = element;
  429.     return *this;
  430. }
  431.  
  432. /****************************************************************************/
  433.  
  434. template <class Element>
  435. inline KPSet<Element> &
  436. KPSet<Element>::operator=(const KPList<Element> &list)
  437. {
  438.     my_list = list;
  439.     if (my_list.size() > 1) {
  440.         my_list.sort();
  441.         KPIterator<Element> iter(my_list); 
  442.         register const Element *prev = iter.ptr();
  443.         for (iter++; iter.ptr(); iter++)
  444.             if (*iter == *prev)
  445.                 iter.remove_current();
  446.             else
  447.                 prev = iter.ptr();
  448.     }
  449.     return *this;
  450. }
  451.  
  452. /****************************************************************************/
  453.  
  454. template <class Element>
  455. inline const KPList<Element> &
  456. KPSet<Element>::list() const
  457. {
  458.     return my_list;
  459. }
  460.  
  461. /****************************************************************************/
  462.  
  463. template <class Element>
  464. inline int
  465. KPSet<Element>::size() const
  466. {
  467.     return my_list.size();
  468. }
  469.  
  470. /****************************************************************************/
  471.  
  472. template <class Element>
  473. inline bool
  474. KPSet<Element>::is_empty() const
  475. {
  476.     return my_list.is_empty();
  477. }
  478.  
  479. /****************************************************************************/
  480.  
  481. template <class Element>
  482. bool
  483. KPSet<Element>::contains(const KPSet<Element> &set) const
  484. {
  485.     if (this == &set)
  486.         return true;
  487.  
  488.     KPReadOnlyIterator<Element> a(my_list), b(set.my_list);
  489.  
  490.     while (b.ptr()) {
  491.         while (a.ptr() && *a < *b)
  492.             a++;
  493.         if (!(a.ptr() && *a == *b))
  494.             return false;
  495.         a++;
  496.         b++;
  497.     }
  498.  
  499.     return true;
  500. }
  501.  
  502. /****************************************************************************/
  503.  
  504. template <class Element>
  505. bool
  506. KPSet<Element>::contains(const Element &element) const
  507. {
  508.     KPReadOnlyIterator<Element> iter(my_list);
  509.  
  510.     while (iter.ptr() && *iter < element)
  511.         iter++;
  512.     return (iter.ptr() && *iter == element);
  513. }
  514.  
  515. /****************************************************************************/
  516.  
  517. template <class Element>
  518. inline KPSet<Element>
  519. KPSet<Element>::all_such_that(bool (*f)(const Element &)) const
  520. {
  521.     KPSet<Element> new_set;
  522.     new_set.my_list = my_list.all_such_that(f);
  523.     return new_set;
  524. }
  525.  
  526. /****************************************************************************/
  527.  
  528. template <class Element>
  529. Element
  530. KPSet<Element>::retrieve()
  531. {
  532.     if (my_list.is_empty()) {
  533.         cerr << "KPSet: retreive() - set empty\n";
  534.         exit(EXIT_FAILURE);
  535.     }
  536.  
  537.     Element element = my_list.head();
  538.     my_list.remove_head();
  539.     return element;
  540. }
  541.  
  542. /****************************************************************************/
  543.  
  544. template <class Element>
  545. inline KPSet<Element> &
  546. KPSet<Element>::clear()
  547. {
  548.     my_list.clear();
  549.     return *this;
  550. }
  551.  
  552. /****************************************************************************/
  553.  
  554. #endif /* KP_SET_DEFINED */
  555.